package org;

public class NodeReverse {

    public static void main(String[] args) {
        // 创建链表 1 -> 2 -> 3 -> 4 -> 5
        ListNode head = new ListNode(1);
        head.next = new ListNode(2);
        head.next.next = new ListNode(3);
        head.next.next.next = new ListNode(4);
        head.next.next.next.next = new ListNode(5);

        // 翻转链表
        ListNode reversedHead = reverseListDg(head);

        // 输出翻转后的链表
        ListNode current = reversedHead;
        while (current != null) {
            System.out.print(current.val + " ");
            current = current.next;
        }
    }

    //迭代方式翻转链表
    public static ListNode reverseListDd(ListNode head) {
        ListNode prev = null; // 上一个节点
        ListNode current = head; // 当前节点
        ListNode next = null; // 后一个节点

        while (current != null) {
            next = current.next; // 暂存当前节点的下一个节点
            current.next = prev; // 将当前节点的 next 指向前一个节点
            prev = current; // 将 prev 更新为当前节点
            current = next; // 移动到下一个节点
        }

        return prev; // prev 将是新的头节点
    }


    //递归方式翻转链表
    public static ListNode reverseListDg(ListNode head) {
        // 基本情况：如果链表为空或只有一个节点，直接返回该节点
        if (head == null || head.next == null) {
            return head;
        }

        // 通过递归翻转后面的链表
        ListNode newHead = reverseListDg(head.next);

        // 反转当前节点的指针
        head.next.next = head;
        head.next = null; // 当前节点的 next 指向 null，防止循环

        return newHead; // 返回新的头节点
    }

}


class ListNode {
    int val;
    ListNode next;

    ListNode(int x) {
        val = x;
        next = null;
    }
}